#include <iostream>

#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <vector>


struct LockInfo {
    uint64_t row_id_;
    uint64_t owner_tx_;
    std::vector<uint64_t> waiting_txs_;
};


bool DetectDeadLock(std::vector<LockInfo> &lks) {
    //记录每个事务 被 多少个事务等待
    std::unordered_map<uint64_t, std::unordered_set<uint64_t>> ins;

    //记录每个事务的出点集合。
    std::unordered_map<uint64_t, std::unordered_set<u_int64_t>> outs;
    for (int i = 0; i< lks.size(); i++) {
        auto &lk = lks[i];
        //将所有得指向当前事务得事务加入
        for (auto wt : lk.waiting_txs_) {
            ins[lk.owner_tx_].insert(wt);

        }
    }

    int count = 0;
    std::queue<uint64_t> q;
    for (auto [txn_id, in_set] : ins) {
        if (in_set.size() == 0) {
            q.push(txn_id);
            count++;
        }
    }
    //
    //如果没有一个事务 有 出现 : 没有被等待， 那么肯定死锁。
    if (q.size() == 0) {
        return true;
    }

    //此时， ins里面为所有 事务 到 入点信息的映射。
    while (q.size()) {
        auto txn_id = q.front();
        //遍历当前事务的所有出点， 将出点对应的入点减去
        for (auto out : outs[txn_id]) {
            ins[out].erase(txn_id);
            if (ins[out].size() == 0) {
                q.push(out);
                count++;
            }
        }
    }
    //如果加入到queue中， 代表不成环， 0
    return count != lks.size();
}